package com.leetcode.algs4.graph.mst;

import com.leetcode.algs4.graph.Bag;

/**
 * @author Dennis Li
 * @date 2020/6/18 19:01
 */
public class EdgeWeightGraph {
    private final int V;
    private int E; // 边的总数
    private Bag<Edge>[] adj;

    public EdgeWeightGraph(int V) {
        this.V = V;
        this.E = 0;
        adj = (Bag<Edge>[]) new Bag[V];
        for (int v = 0; v < V; v++) {
            adj[v] = new Bag<>();
        }
    }

    public int V() {
        return V;
    }

    public int E() {
        return E;
    }

    public void addEdge(Edge e) {
        // 获取两个节点集
        int v = e.either(), w = e.other(v);
        // adj中现在保存的是边集，将与顶点连接的边e加入集合+中
        adj[v].add(e);
        adj[w].add(e);
        E++;
    }

    public Iterable<Edge> adj(int v) {
        return adj[v];
    }

    public Iterable<Edge> edges() {
        Bag<Edge> bag = new Bag<>();
        for (int v = 0; v < V; v++) {
            for (Edge edge : adj[v]) {
                // 不等，说明这条边有一个可达的顶点，加入到背包中
                if (edge.other(v) != v) bag.add(edge);
            }
        }
        return bag;
    }

}
